
/*
Description:
Given an array consists of non-negative integers, your task is to count the number of triplets 
chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:
The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].
*/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
	//Pointers O(N2)
	int triangleNumber(vector<int>& a) {
		int res = 0;
		sort(a.begin(), a.end());
		reverse(a.begin(), a.end());    // a is decreasing
		for (unsigned int i = 0; i + 2 < a.size(); i++) {
			for (unsigned int j = i + 1, k = a.size() - 1; j < k; j++) {
				while (j < k && a[j] + a[k] <= a[i]) {
					k--;
				}
				res += k - j;
			}
		}
		return res;
	}

	//Binary Search O(N2lgN)
	//You can just use std::lower_bound() instead of implementing the binary search yourself.
	int triangleNumber2(vector<int>& a) {
		int n = a.size();
		sort(a.begin(), a.end());
		int res = 0;
		for (int i = 0; i < n - 2; i++) {
			for (int j = i + 1; j < n - 1; j++) {
				int sum = a[i] + a[j];   // the sum of 2 shortest sides;
				int firstGE = firstGreatOrEqual(a, j + 1, sum);
				res += firstGE - 1 - j;
			}
		}
		return res;
	}


	int firstGreatOrEqual(vector<int>& a, int i0, int target) {
		int lo = i0, hi = a.size();
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (a[mid] < target) {
				lo = mid + 1;
			}
			else {
				hi = mid;
			}
		}
		return hi;
	}

	int triangleNumber1(vector<int>& nums) {
		vector<int> snums(nums);
		sort(snums.begin(), snums.end());
		int count = 0;
		for (int n = nums.size(), k = n - 1; k > 1; --k) {
			int i = 0, j = k - 1;
			while (i < j) {
				// any value x between i...j will satisfy snums[x] + snums[j] > snums[k]
				// and because snums[k] > snums[j] > snums[x] >= 0, they will always satisfy
				// snums[k] + snums[x] > snums[j] and snums[k] + snums[j] > snums[x]
				if (snums[i] + snums[j] > snums[k])
					count += --j - i + 1;
				else
					++i;
			}
		}
		return count;
	}

	int triangleNumber0(vector<int>& nums) 
	{
		int count = 0;
		int a = 0, b = 0, c = 0;
		int flag[1000] = { 0 };
		
		int len = nums.size();

		for (int i=0;i<len;i++)
		{
			a = nums[i];
			memset(flag, 0, len*sizeof(int));
		
			for (int j = 0; j < len; j++)
			{
				if ((j == i) || (flag[j] == 1))
					continue;
				b = nums[j];
				flag[j] = 1;

				//memset(flagc, 0, len * sizeof(int));
				for (int k = 0; k < len; k++)
				{
					if ((k == i) || (k == j) || (flag[k] == 1))
						continue;
					c = nums[k];
					flag[k] = 1;
					if (isTriangle(a, b, c))
					{
						count++;
						cout << "a: " << a << " b: " << b << " c: " << c << endl;
					}						
				}
			}
		}
		return count;
	}

	bool isTriangle(int a, int b, int c)
	{
		if ((a + b > c) && (a + c > b) && (b + c > a))
			return true;

		return false;
	}
};

int _triangleNumber()
{
	vector<int> case1{2,2,3,4};
	vector<int> nums(case1);
	int count;
	Solution solu;
	
	count = solu.triangleNumber(nums);

	cout << "nums: " <<endl;
	for (auto num : nums)
	{
		cout << num << " ";
	}
	cout << endl;

	cout << "count: " << count << endl;
	return 0;
}